const common = require('./base/common');

/**
 * 115. 不同的子序列
 * 
 * 思路：构造一个二维状态表，计算
 * 当 t[i - 1] == s[j - 1], dp[i][j]=dp[i-1][j-1]+dp[i][j-1]; 
 * <删减模式，删减s中多少个字符可以得到除当前字符以外的前缀串。>
 * 不相等则，dp[i][j]=dp[i][j-1]; 
 * <传递模式，表示前串包含多少个当前匹配的串。>
 * 
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function(s, t) {
    let dp = [];
    for(let i=0; i <= t.length; ++i) {
        dp.push(new Array(s.length + 1).fill(0));
    }
    dp[0] = new Array(s.length + 1).fill(1);

    for(let i=1; i <= t.length; ++i) {
        for(let j=1; j <= s.length; ++j) {
            if(t[i - 1] == s[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
            } else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }

    return dp[t.length][s.length];
};

common.testing([
    ["rabbbit", "rabbit"],
    ["babgbag", "bag"]
])(args => numDistinct(args[0], args[1]));